1. Field of the Invention
The present invention relates to the field of cryptographic systems; and specifically, to the field of sharing secrets amongst more than one person.
2. Background of the Invention
Secret sharing is an important problem in cryptography. Several solutions have been proposed in the literature. A general version of this problem (known as the k out of n secret sharing problem) can be stated as follows. There is a secret S that has to be shared among n persons such that any k of them will be able to retrieve S uniquely. Fewer than k persons will not be able to construct S.
Some of the secret sharing solutions proposed in the literature have the property that portions of the secret given to the individuals will not correspond to portions of the secret. This is a desirable property. Existing techniques suffer from the following problem. It is conceivable that the persons carrying portions of the secret are geographically distributed. In the reconstruction of the secret by a custodian, the portions might be coming in at different times, and it may be necessary to store the portions on a disk until the last piece comes in. This will be cause for concern since an intruder may be able to probe the disk to collect the various pieces and hence reconstruct the secret.
For example, consider electronic banking. One of the services that banks provide is an electronic safety box. The box may contain documents shared by many persons. If the persons sharing a specific document are geographically distributed, their portions might come in at different times thus necessitating the storage of various portions in the disk. A malicious bank employee might probe the disk to collect the portions and reconstruct the secret. Consider the sharing of a secret by three persons A, B, and C. On one invocation of reconstruction, A might be the first person to send his portion, which is stored on the disk. On a second invocation, C might be the first person to send her message, etc. A malicious employee who watches all the invocations might get all the portions and hence might be able to retrieve the secret. This sort of attack is deemed “the disk attack”.
The disk attack can be avoided by encrypting the pieces before storing them on the disk. However, this is a costly solution in terms of computation time since we have to spend time for reconstructing S and also for encryption and decryption.